package com.sfx.算法专题.排序.mergesort;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-09-07
 * Time: 8:52
 */
public class Code_1_reversePairs {

    static class Solution {
        private int[] tmp;

        public int mergeSort(int[] nums, int left, int right) {
            if (left >= right) return 0;
            int mid = (left + right) / 2;
            int res = 0;
            res += mergeSort(nums, left, mid);
            res += mergeSort(nums, mid + 1, right);
            // 进行计算逆序对
            // 利用数组的有序性,使用同向双指针,来计算逆序对的个数
            int cur1 = left, cur2 = mid + 1;
            while (cur1 <= mid && cur2 <= right) {
                if (nums[cur1] / 2.0 > nums[cur2]) {
                    // nums[cur1] > 2*nums[cur2];
                    res += (right - cur2 + 1);
                    cur1++;
                } else {
                    cur2++;
                }
            }
            cur1 = left;
            cur2 = mid + 1;
            int i = 0;
            while (cur1 <= mid && cur2 <= right) {
                if (nums[cur1] > nums[cur2]) {
                    tmp[i++] = nums[cur1++];
                } else {
                    tmp[i++] = nums[cur2++];
                }
            }
            while (cur1 <= mid) {
                tmp[i++] = nums[cur1++];
            }
            while (cur2 <= right) {
                tmp[i++] = nums[cur2++];
            }
            // 拷贝回原数组
            for (int j = left; j <= right; ++j) {
                nums[j] = tmp[j - left];
            }
            return res;
        }

        public int reversePairs(int[] nums) {
            tmp = new int[nums.length];
            return mergeSort(nums, 0, nums.length - 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[]{2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647};
        solution.reversePairs(arr);
    }
}
